/**
 * https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
 * 二叉树的层平均值
 * @param root 
 */
const averageOfLevels = (root: TreeNode | null): number[] => {
    if (root === null) return []
    const ans: number[] = []

    const stack: TreeNode[] = []

    // 默认是第一层
    let level = 1,
        count = 1,
        curSum = 0;

    // 将根放入栈中
    stack.push(root);

    while (stack.length > 0) {
        const n = stack.shift()!;
        level--;
        curSum += n.val;
        count++
        // 左子树不为空
        if (n.left !== null) stack.push(n.left)

        // 右子树不为空
        if (n.right !== null) stack.push(n.right)

        // 当前层已经遍历完了, 开始计算平均值
        if (level == 0) {
            // 当前栈中的数量就是下一层的层数
            count = level = stack.length;

            // 计算平均值
            ans.push(curSum / count)

            // 回复总和
            curSum = 0;
        }
    }

    return ans;

};